LoginSignup
pomodoro_
@pomodoro_ (pomodoro)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

黄金分割探索　ARC054B - ムーアの法則

Q&AClosed
C++アルゴリズムAtCoder競技プログラミング

WAの原因が分かりません。

競技プログラミングの初心者です。
ARC054B - ムーアの法則を解きました。三分探索を使ったコードではACできましたが、三分探索より効率の良い方法として黄金分割探索があることをネットで知り、そちらでも解いてみたいと思いました。
しかし、書いてみたコードでは入力に対して期待されるものとは異なるものが出力されてしまいます。ChatGPTに聞いてみるなどしたのですが解決できませんでした。原因を教えてほしいです。
三分探索でACしたコードも載せておきました。

ソースコード　（黄金分割探索・WA）　＊4/30修正

#include <bits/stdc++.h>
using namespace std;

double P;

double f(double x) {
  return x + P / pow(2, x / 1.5);
}

int main() {
  cin >> P;
  
  double gold = (1 + sqrt(5)) / 2;
  
  double l = 0, r = P;
  double c1 = (l * gold + r) / (1 + gold);
  double c2 = (l + r * gold) / (1 + gold);
  double f_c1 = f(c1);
  double f_c2 = f(c2);
  while (r - l > 0.00000001) {
    if (f_c1 > f_c2) {
      l = c1;
      c1 = c2;
      f_c1 = f_c2;
      c2 = (l * gold + r) / (1 + gold);
      f_c2 = f(c2);
    }
    else {
      r = c2;
      c2 = c1;
      f_c2 = f_c1;
      c1 = (l + r * gold) / (1 + gold);
      f_c1 = f(c1);
    }
  }
  
  cout << fixed << setprecision(10) << f(l) << endl;
}

入力例１→ 実際の出力

2.8798910904

入力例２→ 実際の出力

0.0400000000

入力例３→ 実際の出力

447213595499958336.0000000000

ソースコード　（三分探索・AC）

#include <bits/stdc++.h>
using namespace std;

double P;

double f(double x) {
  return x + P / pow(2, x / 1.5);
}

int main() {
  cin >> P;
  
  double l = 0, r = P;
  while (r - l > 0.00000001) {
    double c1 = (2 * l + r) / 3;
    double c2 = (l + 2 * r) / 3;
    
    if (f(c1) > f(c2)) l = c1;
    else r = c2;
  }
  
  cout << fixed << setprecision(10) << f(l)<< endl;
}
0

2Answer

nak435
@nak435

自分は 黄金分割探索 をよく知りませんが、↓こちらの記事を参考に書き換えてみました。

三分探索の次の2行のみを書き換え（でAC）
    double c1 = (l * gold + r) / (1.0 + gold);
    double c2 = (l + r * gold) / (1.0 + gold);
1
actorbug
@actorbug

どうして初回とそれ以降とで計算式を変えてしまったのでしょうか。

#include <bits/stdc++.h>
using namespace std;

double P;

double f(double x) {
  return x + P / pow(2, x / 1.5);
}

int main() {
  cin >> P;
  
  double gold = (1 + sqrt(5)) / 2;
  
  double l = 0, r = P;
  double c1 = (l * gold + r) / (1 + gold);
  double c2 = (l + r * gold) / (1 + gold);
  double f_c1 = f(c1);
  double f_c2 = f(c2);
  while (r - l > 0.00000001) {
    if (f_c1 > f_c2) {
      l = c1;
      c1 = c2;
      f_c1 = f_c2;
-     c2 = (l * gold + r) / (1 + gold);
+     c2 = (l + r * gold) / (1 + gold);
      f_c2 = f(c2);
    }
    else {
      r = c2;
      c2 = c1;
      f_c2 = f_c1;
-     c1 = (l + r * gold) / (1 + gold);
+     c1 = (l * gold + r) / (1 + gold);
      f_c1 = f(c1);
    }
  }
  
  cout << fixed << setprecision(10) << f(l) << endl;
}
1

Comments

  1. @pomodoro_

    Questioner

    ありがとうございます！！！
    全然気付けなくて困っていました。ACできました！

Your answer might help someone💌

LoginSign Up

Popular Questions